#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution01 {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        // 只要入栈的顶部元素不等于pop的顶部元素，则一直入栈
        // 只要相等，则两个都出栈
        // stack<int> stpop, stpush;
        // for (int i = popped.size() - 1; i >= 0; i--) 
        //     stpop.push(popped[i]);
        // // 只有最后两个都为空之后，才会返回 true
        // int i = 0, len = pushed.size();
        // while (i < len || i == len) {
        //     if (!stpush.empty() && stpop.top() == stpush.top()) {
        //         stpop.pop();
        //         stpush.pop();
        //     } else {
        //         if (i < len) {
        //             stpush.push(pushed[i]);
        //             i++;
        //         } else {
        //             break;
        //         }

        //     }           
        // }
        // return stpop.empty();

        stack<int> st;
        int index = 0, len = popped.size();
        for (int i = 0; i <= pushed.size(); i++) {
            if (i <= pushed.size()) {
                while (!st.empty() && index < len && st.top() == popped[index]) {
                    st.pop();
                    index++;
                }
                if (i == pushed.size()) break;
            }

            if (i < pushed.size())
                st.push(pushed[i]);                
        }
        return index == len;
    }
};

// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

class Solution02 {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> ret;
        if (root == nullptr) return ret;
        queue<Node*> qN;
        qN.push(root);
        // 使用一个变量记录没层的节点个数
        int nodenum = 1;
        while (!qN.empty()) {
            // 先取出一个元素
            vector<int> add;
            int num = 0;
            while (nodenum--) {
                Node* cur = qN.front();
                qN.pop();
                add.push_back(cur->val);
                for (auto& node : cur->children) {
                    if (node != nullptr) {
                        num++;
                        qN.push(node);
                    }
                }
            }
            ret.push_back(add);
            nodenum = num;  
        }
        return ret;
    }
};

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution03 {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if (root == nullptr) return ret;
        queue<TreeNode*> qTree;
        qTree.push(root);
        int rever = 1;
        while (!qTree.empty()) {
            int sz = qTree.size();
            vector<int> add;
            for (int i = 0; i < sz; i++) {
                TreeNode* cur = qTree.front();
                qTree.pop();
                add.push_back(cur->val);
                if (cur->left) qTree.push(cur->left);
                if (cur->right) qTree.push(cur->right);
            }
            if (rever % 2 == 0)
                reverse(add.begin(), add.end());
            rever++;
            ret.push_back(add);
        }
        return ret;
    }
};

class Solution04 {
public:
    int widthOfBinaryTree(TreeNode* root) {
        // vector<pair<TreeNode*, unsigned int>> v;
        // int index = 0;
        // v.emplace_back(make_pair(root, 1));
        // unsigned int ret = 1;
        // while (index < v.size()) {
        //     ret = max(ret, v.back().second - v[index].second + 1);
        //     int sz = v.size() - index;
        //     for (int i = 0; i < sz; i++) {
        //         pair<TreeNode*, unsigned int> cur = v[index++];
        //         TreeNode* node = cur.first;
        //         unsigned int j = cur.second;
        //         if (node->left) 
        //             v.emplace_back(make_pair(node->left, 2 * j));
                
        //         if (node->right) 
        //             v.emplace_back(make_pair(node->right, 2 * j + 1));
        //     }

        // }
        // return ret;
        vector<pair<TreeNode*, unsigned int>> v;
        unsigned int ret = 0;
        v.push_back({root, 1});
        while (!v.empty()) {
            auto& [x1, y1] = v[0];
            auto& [x2, y2] = v.back();
            ret = max(ret, y2 - y1 + 1);
            vector<pair<TreeNode*, unsigned int>> temp;
            for (auto& [x, y] : v) {
                if (x->left) temp.push_back({x->left, 2 * y});
                if (x->right) temp.push_back({x->right, 2 * y + 1});
            }
            v = temp;
        }
        return ret;
    }
};

class Solution05 {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> ret;
        if (root == nullptr) return ret;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int maxelement = INT_MIN;
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                TreeNode* t = q.front();
                maxelement = max(maxelement, t->val);
                q.pop();
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
            ret.push_back(maxelement);
        }
        return ret;
    }
};

class Solution06 {
public:
    int lastStoneWeight(vector<int>& stones) {
    
        priority_queue<int> pq;
        for (auto& e : stones)
            pq.push(e);
        // while (!pq.empty()) {
        //     cout << pq.top() << endl;
        //     pq.pop();
        // }
        while (pq.size() > 1) {
            int larger = pq.top();
            pq.pop();
            int smaller = pq.top();
            pq.pop();
            if (larger - smaller > 0) pq.push(larger - smaller);
            
        }
        if (pq.empty())
            return 0;
        else 
            return pq.top();
    }
};

struct Com {
    bool operator()(int x, int y) {
        return x < y;
    }
};

class KthLargest {
    // static bool com(int x, int y) {
    //     return x > y;
    // }
public:
    KthLargest(int k, vector<int>& nums) {
        _k = k;
        _nums = nums;
        sort(_nums.begin(), _nums.end(), Com());
        // for (auto e : nums) _pq.push(e);
        // if (k < nums.size()) {
        //     while (_pq.size() != k) {
        //         _pq.pop();
        //     }
        // }
        for (auto e : _nums) {
            _pq.push(e);
            if (_k < _pq.size()) _pq.pop();
        }
        
    }
    
    int add(int val) {
        // _pq.push(val);
        // vector<int> temp;
        // int num = _k - 1;
        // while (num--) {
        //     temp.push_back(_pq.top());
        //     _pq.pop();
        // }
        // int ret = _pq.top();
        // for (auto& t : temp) _pq.push(t);
        // return ret;
        _nums.push_back(val);
        // _pq.push(val);
        // while (_pq.size() != _k) _pq.pop();
        // return _pq.back();
        // if (val > _pq.top()) {
        //     _pq.pop();
        //     _pq.push(val);
        // }
        // return _pq.top();
        _pq.push(val);
        if (_pq.size() > _k) _pq.pop();
        return _pq.top();
    }
private:
    int _k;
    // 需要建立小根堆
    priority_queue<int, vector<int>, greater<int>> _pq;
    vector<int> _nums;
};


class Solution07 {
    using fun = pair<string, int>;
    struct com {
        bool operator()(const fun& x, const fun& y) {
            return (x.second > y.second) || (x.second == y.second && x.first < y.first);
        }
    };

public : 
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> hash;
        for (auto& s : words)
            hash[s]++;
        
        priority_queue<fun, vector<fun>, com> pq;
        for (auto e : hash) {
            pq.push(e);
            if (pq.size() > k) pq.pop();
        }
        // 将数据拿出来

        vector<string> ret;
        while (!pq.empty()) {
            ret.push_back(pq.top().first);
            pq.pop();
        }

        reverse(ret.begin(), ret.end());
        return ret;
    }
};

class MedianFinder {
public:
    MedianFinder() {

    }
    
    void addNum(int num) {
        // if (_leftheap.empty()) {
        //     _leftheap.push(num);
        //     return;
        // }
        // if (_rightheap.empty()) {
        //     _rightheap.push(num);
        //     return;
        // }

        if (_rightheap.size() == _leftheap.size()) {
            // 将其放在左边
            if (_leftheap.empty() || num <= _leftheap.top()) {
                _leftheap.push(num);
            } else {
                _rightheap.push(num);
                _leftheap.push(_rightheap.top());
                _rightheap.pop();
            }
        } else {
            if (num <= _leftheap.top()) {
                _leftheap.push(num);
                _rightheap.push(_leftheap.top());
                _leftheap.pop();
            } else {
                _rightheap.push(num);
            }
        }
    }
    
    double findMedian() {
        if (_leftheap.size() == _rightheap.size())
            return (_leftheap.top() + _rightheap.top()) / 2.0 ;
        else 
            return _leftheap.top();
    }
private:
    priority_queue<int, vector<int>, greater<int>> _rightheap;   // 右边创建小堆
    priority_queue<int, vector<int>, less<int>> _leftheap; // 左边创建大堆
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

int main() {
    // 对于大小堆的创建，小根堆里比较逻辑为大于，大根堆的比较逻辑为小于

    return 0;
}